/***************************************************************************
 * File name: q2.c
 *
 * Authors:  Tomer Filiba		Reuven Horon
 *           037013075			066729740
 *           sebulba@t2			sreuvenh@t2
 *
 * Exercise #: 5
 * Question #: 2
 * Submission Date: 2/8/07
 **************************************************************************/

/*-------------------------------------------------------------------------
 * Include files:
 *------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>


/*=========================================================================
  Constants and definitions:
==========================================================================*/
#define SUCCESS				(0)
#define FAILURE				(1)
#define	ALPHABET_LENGTH		(26)

typedef enum {
	FALSE = (0 == 1),
	TRUE = (0 == 0),
} bool_t;


/*=========================================================================
  Global variables:
==========================================================================*/
char *tb_names[] = {"Eli Ben-Sasson", "Saher Esmeir", "Itai Sharon", "Andrey Klinger",
                    "Elad Haramaty", "Iddo Hanniel", "Miri Ben-Chen", "Osnat Tal",
                    "Sasha Skolozub", "Eli Biham", "Michael Elad", "Itai Dabran",
                    "Iddo Bentov", "Michael Heymann", "Michael Kaminski",
                    "Michael Lindenbaum", "Michael Shmoish"};
int tb_numbers[] = {4892, 4951, 4946, 3383, 5652, 3896, 4347, 4897, 4960, 4308, 4169, 
                    2908, 3372, 4163, 4360, 4331, 4302};


/*=========================================================================
  Forward declarations:
==========================================================================*/
bool_t check_alphabet(const char * alphabet);
void resequence(const char * alphabet, char * charmap);
bool_t is_preceeding(const char * s1, const char * s2, const char * charmap);
void sort_tb_by_name(char ** tb_names, int * tb_numbers, int tb_size,
					 const char * alphabet);
bool_t startswith(const char * s1, const char * s2);
int search_tb(const char * name, char ** tb_names, int tb_size, 
			  const char * alphabet);
bool_t interactive_search(char ** tb_names, int * tb_numbers, int tb_size, 
						  char * alphabet);


/*=========================================================================
  Function implementation:
==========================================================================*/

/*-------------------------------------------------------------------------
 * validates the alphabet
 *
 * parameters:
 * - alphabet - an array of 26 unique, lower-case letters, which specify
 *   the new order of the alphabet letters.
 *
 * return value: TRUE if the alphabet is valid, FALSE otherwise
 *------------------------------------------------------------------------*/
bool_t check_alphabet(const char * alphabet)
{
	int i;
	char ch;
	bool_t used[ALPHABET_LENGTH] = {FALSE};
	
	if (strlen(alphabet) != ALPHABET_LENGTH) {
		printf("Error! alphabeth must contain %d letters\n", ALPHABET_LENGTH);
		return FALSE;
	}
	
	for (i = 0; i < ALPHABET_LENGTH; i++) {
		ch = alphabet[i];
		if (ch < 'a' || ch > 'z') {
			printf("Error! alphabeth letters must be a..z, found '%c'\n", ch);
			return FALSE;
		}
		if (used[ch - 'a']) {
			printf("Error! letter '%c' given more than once\n", ch);
			return FALSE;
		}
		used[ch - 'a'] = TRUE;
	}
	
	return TRUE;
}

/*-------------------------------------------------------------------------
 * resequences the charmap, sorted by the new alphabet
 *
 * parameters:
 * - alphabet - an array of 26 unique, lower-case letters, which specify
 *   the new order of the alphabet letters.
 * - charmap - an array of 256 chars, which will be sorted by the new order
 *   of the alphabet (output parameter)
 *
 * return value: none
 *------------------------------------------------------------------------*/
void resequence(const char * alphabet, char * charmap)
{
	int i;
	
	for (i = 0; i < 256; i++) {
		if (i >= 'a' && i <= 'z') {
			charmap[alphabet[i - 'a']] = i;
		}
		else if (i >= 'A' && i <= 'Z') {
			charmap[alphabet[i - 'A'] - 'a' + 'A'] = i;
		}
		else {
			charmap[i] = i;
		}
	}
}

/*-------------------------------------------------------------------------
 * determines if one string preceeds another according to the new alphabet
 * order
 *
 * parameters:
 * - s1 - the first string
 * - s2 - the second string
 * - charmap - an array of 256 chars, ordered according to the new alphabet
 *
 * return value: TRUE if s1 preceeds s2, FALSE otherwise
 *------------------------------------------------------------------------*/
bool_t is_preceeding(const char * s1, const char * s2, const char * charmap)
{
	int i, len1, len2;
	char c1, c2;
	
	len1 = strlen(s1);
	len2 = strlen(s2);
	for (i = 0; i < len1 && i < len2; i++) {
		c1 = charmap[s1[i]];
		c2 = charmap[s2[i]];
		if (c1 < c2) {
			return TRUE;
		}
		else if (c1 > c2) {
			return FALSE;
		}
		/* continue only if c1 == c2 */
	}
	return FALSE;
}

/*-------------------------------------------------------------------------
 * sorts the phonebook entries according to the new alphabet order.
 * notes: this is an in-place sort in O(N^2) time complexity
 *
 * parameters:
 * - s1 - the first string
 * - s2 - the second string
 * - charmap - an array of 256 chars, ordered according to the new alphabet
 *
 * return value: TRUE if s1 preceeds s2, FALSE otherwise
 *------------------------------------------------------------------------*/
void sort_tb_by_name(char ** tb_names, int * tb_numbers, int tb_size,
					 const char * alphabet)
{
	int i, j, k, tmp_number;
	char *smallest, *tmp_name;
	char charmap[256];
	
	resequence(alphabet, charmap);
	
	for (i = 0; i < tb_size; i++) {
		smallest = tb_names[i];
		k = -1;
		for (j = i + 1; j < tb_size; j++) {
			if (is_preceeding(tb_names[j], smallest, charmap)) {
				smallest = tb_names[j];
				k = j;
			}
		}
		
		/* swap name and number */
		if (k == -1)
			continue;
		tmp_name = tb_names[i];
		tb_names[i] = tb_names[k];
		tb_names[k] = tmp_name;
		tmp_number = tb_numbers[i];
		tb_numbers[i] = tb_numbers[k];
		tb_numbers[k] = tmp_number;
	}
}

/*-------------------------------------------------------------------------
 * determines if one string starts with another string 
 *
 * parameters:
 * - s1 - the first string (possibly contains s1)
 * - s2 - the second string (possibly contained in s2)
 *
 * return value: TRUE if s1 begins with s2, FALSE otherwise
 *------------------------------------------------------------------------*/
bool_t startswith(const char * s1, const char * s2)
{
	int i, len1, len2;
	
	len1 = strlen(s1);
	len2 = strlen(s2);
	if (len1 < len2) {
		return FALSE;
	}
	for (i = 0; i < len2; i++) {
		if (s1[i] != s2[i]) {
			return FALSE;
		}
	}
	return TRUE;
}

/*-------------------------------------------------------------------------
 * searches the telephone book, sorted by the new alphabet
 * notes: this is a O(log(N)) search
 *
 * parameters:
 * - name - the full name, or part of the name, of the entry to search
 * - tb_names - the sorted array of telephone book names
 * - tb_size - the number of entries in the phonebook
 * - alphabet - the new alphabet order
 *
 * return value: the index of the entry, or -1 if the entry does not exist
 *------------------------------------------------------------------------*/
int search_tb(const char * name, char ** tb_names, int tb_size, 
			  const char * alphabet)
{
	int i, low = 0, high = tb_size;
	char charmap[256];
	
	resequence(alphabet, charmap);
	
	for (i = tb_size / 2; tb_size != 0; tb_size /= 2) {
		if (is_preceeding(name, tb_names[i], charmap)) {
			high = i;
		}
		else if (startswith(tb_names[i], name)) {
			while (i >= 0 && startswith(tb_names[i], name))
				i--;
			return i + 1;
		}
		else {
			low = i;
		}
		i = (low + high) / 2;
	}
	
	return -1;
}

/*-------------------------------------------------------------------------
 * interactive search prompt, searches for a name given by the user
 *
 * parameters:
 * - tb_names - the sorted array of telephone book names
 * - tb_numbers - the sorted array of telephone book numbers
 * - tb_size - the number of entries in the phonebook
 * - alphabet - the new alphabet order
 *
 * return value: TRUE if the function terminates successfully, or FALSE
 * if an error occurs (e.g., EOF)
 *------------------------------------------------------------------------*/
bool_t interactive_search(char ** tb_names, int * tb_numbers, int tb_size, 
						  char * alphabet)
{
	int i;
	char charmap[256];
	char name[80];
	
	resequence(alphabet, charmap);
	
	while (TRUE) {
		printf("Type name to search: ");
		/* read line and process it */
		if (fgets(name, sizeof(name), stdin) == NULL) {
			return FALSE;
		}
		if (name[0] == '\n')
			continue;
		name[strlen(name)-1] = '\0';
		if (strcmp(name, "Log off") == 0) {
			return TRUE;
		}

		/* search name and show results */
		i = search_tb(name, tb_names, tb_size, alphabet);
		if (i == -1) {
			printf("Name not found\n");
		}
		else {
			for (; i < tb_size && startswith(tb_names[i], name); i++) {
				printf("%-30s %d\n", tb_names[i], tb_numbers[i]);
			}
		}
		printf("\n");
	}
}

/*-------------------------------------------------------------------------
 * The main program: take alphabet from command line, sort phonebook, 
 * and allow an interactive prompt for searching names in the phonebook
 *-----------------------------------------------------------------------*/
int main(int argc, const char ** argv)
{
	char * alphabet;
	const int tb_size = sizeof(tb_numbers) / sizeof(tb_numbers[0]);
	
	if (argc != 2) {
		printf("Error! Usage: %s alphabet\n", argv[0]);
		return FAILURE;
	}
	
	alphabet = argv[1];
	if (!check_alphabet(alphabet)) {
		printf("Alphabet is invalid\n");
		return FAILURE;
	}
	
	sort_tb_by_name(tb_names, tb_numbers, tb_size, alphabet);
	if (!interactive_search(tb_names, tb_numbers, tb_size, alphabet)) {
		printf("Error reading stdin\n");
		return FAILURE;
	}
	
	return SUCCESS;
}

/**************************************************************************
			                          End of file
***************************************************************************/
